\documentclass[submission]{FPSAC2017}

\articlenumber{50}
\addbibresource{50_Swanson.bib}

% Packages
\usepackage{amsmath}              % provides \underset, etc.
\usepackage{accents}              % provides \accentset, etc.; must be loaded after amsmath
\usepackage{amsopn,amssymb}       % provides \DeclareMathOperator, \mathbb, etc.
\usepackage{amsthm}
\usepackage{bm}                   % provides \bm for math bold greek letters
\usepackage{bbm}                  % provides \mathbbm, eg. for lower-case blackboard bold characters
\usepackage{enumerate}            % more powerful enumerate environments
\usepackage{microtype}            % nicer text spacing
\usepackage[intoc,refpage]{nomencl}         % make a symbol list
\usepackage{multicol}             % put lists with many short entries into multiple columns
\usepackage{setspace}             % \doublespacing, etc.
\usepackage{shuffle}              % provides \shuffle and \cshuffle
\usepackage{soul}                 % multi-line underlines
\usepackage{thmtools}             % interface to amsthm
\usepackage{tikz-cd}              % nice commutative diagrams; see cd environment below
\usetikzlibrary{calc}             % allow \let's in tikzpicture environments
\usetikzlibrary{positioning}      % allow "above = 1" syntax
\usepackage{xifthen}              % \ifthenelse, \isempty, etc.
\usepackage{subcaption}        % provides subfigure environment, etc.

% Math operators
\DeclareMathOperator{\Ab}{Ab}
\DeclareMathOperator{\alg}{-alg}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\Ass}{Ass}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\cdes}{cdes}
\DeclareMathOperator{\CDes}{CDes}
\DeclareMathOperator{\CDT}{CDT}
\DeclareMathOperator{\Ch}{ch}
\DeclareMathOperator{\Char}{char}
\DeclareMathOperator{\cHom}{\mathcal{H}\textit{om}}
\DeclareMathOperator{\code}{code}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\comaj}{comaj}
\DeclareMathOperator{\cont}{cont}
\DeclareMathOperator{\cmaj}{cmaj}
\DeclareMathOperator{\CT}{CT}
\DeclareMathOperator{\cycle}{cycle}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\exc}{exc}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\fin}{fin}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\Fl}{Fl}
\DeclareMathOperator{\FP}{FP}
\DeclareMathOperator{\Flags}{Flags}
\DeclareMathOperator{\fl}{fl}
\DeclareMathOperator{\flex}{flex}
\DeclareMathOperator{\freq}{freq}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\GKdim}{GKdim}
\DeclareMathOperator{\gl}{gl}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\gldim}{gldim}
\DeclareMathOperator{\gr}{gr}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\GUD}{GUD}
\DeclareMathOperator{\hgt}{ht}
\DeclareMathOperator{\Hilb}{Hilb}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\injdim}{injdim}
\DeclareMathOperator{\Int}{Int}
\DeclareMathOperator{\Kdim}{Kdim}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\lex}{lex}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\mmaj}{mmaj}
\DeclareMathOperator{\Mod}{mod}
\DeclareMathOperator{\myst}{myst}
\DeclareMathOperator{\nil}{nil}
\DeclareMathOperator{\NSYM}{NSYM}
\DeclareMathOperator{\op}{op}
\DeclareMathOperator{\period}{period}
\DeclareMathOperator{\Perm}{Perm}
\DeclareMathOperator{\Perms}{Perms}
\DeclareMathOperator{\Pre}{pre}
\DeclareMathOperator{\projdim}{projdim}
\DeclareMathOperator{\pt}{pt}
\DeclareMathOperator{\QH}{QH}
\DeclareMathOperator{\QSYM}{QSYM}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\Rings}{Rings}
\DeclareMathOperator{\row}{row}
\DeclareMathOperator{\RSK}{RSK}
\DeclareMathOperator{\rw}{rw}
\DeclareMathOperator{\sd}{sd}
\DeclareMathOperator{\Sets}{\textit{Sets}}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\Sh}{Sh}
\DeclareMathOperator{\SIT}{SIT}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\SO}{SO}
\DeclareMathOperator{\sort}{sort}
\DeclareMathOperator{\Sp}{Sp}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\spec}{spec}
\DeclareMathOperator{\spin}{spin}
\DeclareMathOperator{\St}{St}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\str}{str}
\DeclareMathOperator{\Supp}{Supp}
\DeclareMathOperator{\SST}{SST}
\DeclareMathOperator{\SSYT}{SSYT}
\DeclareMathOperator{\stat}{stat}
\DeclareMathOperator{\std}{std}
\DeclareMathOperator{\syt}{syt}
\DeclareMathOperator{\SYT}{SYT}
\DeclareMathOperator{\SYM}{SYM}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\ssum}{ssum}
\DeclareMathOperator{\Sum}{sum}
\DeclareMathOperator{\TL}{TL}
\DeclareMathOperator{\Tot}{Tot}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trdeg}{trdeg}
\DeclareMathOperator{\triv}{triv}
\DeclareMathOperator{\UD}{UD}
\DeclareMathOperator{\wgt}{wgt}
\DeclareMathOperator{\word}{word}
\DeclareMathOperator{\Words}{Words}
\DeclareMathOperator{\YUD}{YUD}
% Named ``ilim'' for ``inverse limit'' to avoid conflicting with \lim
\newcommand{\ilim}{\operatornamewithlimits{\underset{\longleftarrow}{lim}}}
% ``dlim'' for ``direct limit''
\newcommand{\dlim}{\operatornamewithlimits{\underset{\longrightarrow}{lim}}}
\newcommand{\mbinom}[2]{\left(\!\!\binom{#1}{#2}\!\!\right)}

% Convenient shortcuts
\newcommand{\bA}{\mathbb{A}}
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bE}{\mathbb{E}}
\newcommand{\bF}{\mathbb{F}}
\newcommand{\bk}{\mathbbm{k}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\fg}{\mathfrak{g}}
\newcommand{\fm}{\mathfrak{m}}
\newcommand{\fn}{\mathfrak{n}}
\newcommand{\fp}{\mathfrak{p}}
\newcommand{\fq}{\mathfrak{q}}
\newcommand{\fS}{\mathfrak{S}}
\newcommand{\fU}{\mathfrak{U}}
\newcommand{\tsub}{\mathrel{\unlhd}}

% Convenient general macros
\newcommand{\mm}{\texttt{--}}
\newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}}
\newcommand{\up}{\mathord{\uparrow}}
\newcommand{\Ind}{\!\!\mathord{\uparrow}}
\newcommand{\res}{\!\!\!\mathord{\downarrow}}
\newcommand{\down}{\mathord{\downarrow}}
\renewcommand{\star}{\mathord{*}}
\newcommand{\too}[1]{\stackrel{#1}{\to}}
\newcommand{\tooo}[2]{\underset{#2}{\overset{#1}{\to}}}
\newcommand{\oo}[3]{\underset{#3}{\overset{#2}{#1}}}
\newcommand{\sline}{\noindent\makebox[\linewidth]{\rule{\linewidth}{0.4pt}}}
\newcommand{\mdy}[1]{\sline\vspace{0.19cm}\\\centering{\Large{\textbf{#1}}}\\\sline}
\newcommand{\ind}{\!\!\uparrow}
\renewcommand{\res}{\!\!\downarrow}
\newcommand{\f}{\frac}
\newcommand{\n}{\f{1}{n}}
\newcommand{\lm}{\lambda}
\newcommand{\lam}{\lambda}
\newcommand{\pa}[1]{{\left( {#1}\right)}}
\newcommand{\ha}{\f{1}{2}}
\newcommand{\sub}{\subset}
\newcommand{\al}{\alpha}
\newcommand{\8}{\infty}
\newcommand{\es}{\emptyset}
\newcommand{\bs}{\bigskip}
\newcommand{\D}{\Delta}
\newcommand{\de}{\delta}
\newcommand{\be}{\beta}
\newcommand{\w}{\omega}
\newcommand{\s}{\sigma}
\newcommand{\si}{\sigma}
\newcommand{\g}{\gamma}
\newcommand{\dd}{\cdot}
\newcommand{\inv}{^{-1}}
\newcommand{\zhat}{\widehat{0}}
\newcommand{\ohat}{\widehat{1}}
\newcommand{\idd}{\accentset{\bullet}{\iota}}
\newcommand{\nur}{\overset{\to}{\nu}}
\newcommand{\nul}{\overset{\gets}{\nu}}
\newcommand{\wt}[1]{\widetilde{#1}}
\newcommand{\tx}{\text}
\newcommand{\sm}{\setminus}
\newcommand{\lp}{\left(}
\newcommand{\rp}{\right)}
\newcommand{\ch}{\binom}
\newcommand{\imp}{\implies}
\newcommand{\va}{\varphi}
\newcommand{\mch}[2]{%
  \mathchoice%
    {\left(\kern-0.48em\ch{#1}{#2}\kern-0.48em\right)}
    {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
    {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
    {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
}

% make subfigure caption identifier lower-case
\captionsetup[subfigure]{labelfont=rm}

% rc-graph macros
\font\co=lcircle10
\def\petit#1{{\scriptstyle #1}}
\def\pes#1#2{\hbox{\rlap{$\petit {#1}_{\scriptscriptstyle #2}$}}
    \phantom{\petit 1}}
\def\plb{\smash{\lower2pt\hbox{\rlap{\vrule height12pt}}
                \raise2pt\hbox{\rlap{\hskip-4pt
                \vrule height.4pt depth0pt width14.7pt}}}}
\def\py{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005} \char'007}}
               \raise6pt\hbox{\rlap{\vrule height4.5pt}}
               \raise2pt\hbox{\rlap{\hskip4pt \vrule height0.4pt depth0pt 
                              width6.5pt}}}}
\def\pe{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005}
                 \phantom{\char'007}}}
               \raise6pt\hbox{\rlap{\vrule height4.5pt}}}}

% Mark Haiman's tableaux macro, modified to put dashed lines around empty boxes
\setlength{\unitlength}{0.06em}
\newlength{\cellsize} \setlength{\cellsize}{18\unitlength}
\newsavebox{\cell}
\sbox{\cell}{\begin{picture}(18,18)
\put(0,0){\line(1,0){18}}
\put(0,0){\line(0,1){18}}
\put(18,0){\line(0,1){18}}
\put(0,18){\line(1,0){18}}
\end{picture}}
\newsavebox{\dashedcell}
\sbox{\dashedcell}{\begin{picture}(18,18)
\multiput(0,0)(5,0){4}{\line(1,0){3}}
\multiput(0,0)(0,5){4}{\line(0,1){3}}
\multiput(18,0)(0,5){4}{\line(0,1){3}}
\multiput(0,18)(5,0){4}{\line(1,0){3}}
\end{picture}}
\newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}%
\ifx\thearg\nothing
\hbox to 0pt{\usebox{\dashedcell} \hss}\else%
\hbox to 0pt{\usebox{\cell} \hss}\fi%
\vbox to \cellsize{
\vss
\hbox to \cellsize{\hss$#1$\hss}
\vss}}
\newcommand\tableau[1]{\vtop{\let\\\cr
\baselineskip -16000pt \lineskiplimit 16000pt \lineskip 0pt
\ialign{&\cellify{##}\cr#1\crcr}}}

\newenvironment{cd}[1][]
  {\begin{center}\begin{tikzcd}[#1]}
  {\end{tikzcd}\end{center}}

% Index/nomenclature configuration and macros
\renewcommand\nomname{List of Symbols}
\newcommand{\bu}[2][]{\framebox{#2}\ifthenelse{\isempty{#1}}{\index{#2}}
    {\index{#1@#2}}}
\newcommand{\mbu}[3][]{\boxed{#2}\nomenclature[$#1$]{$#2$}{#3}}

% Section macros
\newcommand{\Section}[1]{\begin{samepage}\sline\vspace{-0.5cm}\section*{\centering{#1}}\vspace{-0.5cm}\sline
  \addcontentsline{toc}{subsection}{#1}\end{samepage}}
\newcommand{\Subsection}[1]{\subsection*{\centering\color{teal}#1}
  \addcontentsline{toc}{subsection}{#1}}
\newcommand{\Subsubsection}[1]{\subsubsection*{\centering\color{teal}#1}
  \addcontentsline{toc}{subsubsection}{#1}}

\theoremstyle{plain}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Fact}[Theorem]{Fact}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\newtheorem{Question}[Theorem]{Question}

\theoremstyle{definition}
\newtheorem{Notation}[Theorem]{Notation}
\declaretheorem[style=definition,sibling=Theorem]{Definition}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Aside}[Theorem]{Aside}
\newtheorem*{Summary}{Summary}
\newtheorem*{Outline}{Outline}


\title{Standard Tableaux and Modular Major Index}
\author{Joshua P. Swanson}
\address{University of Washington, Seattle, USA\\}

\received{November 13th, 2016}

\abstract{
  We provide simple necessary and sufficient conditions for the
  existence of a standard Young tableau of a given shape and major index $r$
  mod $n$, for all $r$. Our result generalizes the $r=1$ case due essentially to 
  Klyachko (1974) and proves a recent conjecture due to Sundaram
  (2016) for the $r=0$ case. A byproduct of the proof is an asymptotic 
  equidistribution result for ``almost all'' shapes. The proof uses a representation-theoretic
  formula involving Ramanujan sums and normalized symmetric group character estimates.
  Further estimates involving ``opposite'' hook lengths are given which are well-adapted to
  classifying which partitions $\lambda \vdash n$ have $f^\lambda \leq n^d$ for fixed $d$.
}

\keywords{standard Young tableaux, symmetric group characters, major index, hook length formula}


\begin{document}

\maketitle

\section{Introduction}
\label{sec:intro}

Let $\lambda \vdash n$ be an integer partition of size $n$, and let $\SYT(\lambda)$ denote
the set of standard Young tableaux of shape $\lambda$. Let $\maj T$ denote the major index
of $T \in \SYT(\lambda)$, namely the sum of all $i$ for which $i+1$ appears below $i$ (in
English notation). We are chiefly interested in the counts
  \[ a_{\lambda, r} := \#\{T \in \SYT(\lambda) : \maj T \equiv_n r\} \]
where $r$ is taken mod $n$. To avoid giving undue weight to trivial cases, we take $n \geq 1$
throughout. Work due to Klyachko and, later, Kraskiewicz-Weyman, gives the following:

\begin{Theorem}[{\cite[Proposition 2]{klyachko74}}, {\cite{kw01}}]
  \label{thm:kly}
  Let $\lambda \vdash n$ and $n \geq 1$. Then $a_{\lambda, 1}$ is positive except in
  the following cases, when it is zero:
  \begin{itemize}
    \item $\lambda = (2, 2)$ or $\lambda = (2, 2, 2)$;
    \item $\lambda = (n)$ when $n > 1$; or $\lambda = (1^n)$ when $n > 2$.
  \end{itemize}
\end{Theorem}

Indeed, the $a_{\lambda, r}$ have a natural interpretation as irreducible 
multiplicities as follows, a result originally due to Kraskiewicz-Weyman. Let $C_n$ be the cyclic 
group of order $n$ generated by the long cycle $\sigma_n := (1 2 \cdots n) \in S_n$, let
$S^\lambda$ be the
Specht module of shape $\lambda \vdash n$, and let $\chi^r \colon C_n \to \bC^\times$ be
the irreducible representation given by $\chi^r(\sigma_n^i) := \omega_n^{ri}$ where
$\omega_n$ is a fixed primitive $n$th root of unity and $r \in \bZ/n$. Let $\langle -, -\rangle$
denote the standard scalar product for complex representations.

\begin{Theorem}[see {\cite[Theorem~1]{kw01}}]
  \label{thm:mults}
  With the above notation, we have
    \[ \langle S^\lambda, \chi^r\ind_{C_n}^{S_n} \rangle
        = a_{\lambda, r} = \langle \chi^r, S^\lambda\res_{C_n}^{S_n} \rangle. \]
  Moreover, $a_{\lambda, r}$ depends only on $\lambda$ and $\gcd(n, r)$,
  i.e.~if $\gcd(n, r) = \gcd(n, s)$ then $a_{\lambda, r} = a_{\lambda, s}$.
\end{Theorem}

\begin{Remark}
  Kraskiewicz-Weyman gave the first equality in \Cref{thm:mults}, and the second follows by
  Frobenius reciprocity. Klyachko \cite[Proposition 2]{klyachko74} actually determined which
  $S^\lambda$ contain faithful representations of $C_n$ in agreement with \Cref{thm:kly}.
  One may see through a variety of methods that $\chi^r\ind_{C_n}^{S_n}$ depends up to
  isomorphism only on $\gcd(r, n)$.
  
  The manuscript \cite{kw01} was long-unpublished, the delay being largely due to Klyachko
  having already given a significantly more direct proof of their main application, relating
  $\chi^1\ind_{C_n}^{S_n}$ to free Lie algebras, though we have no need of this connection.
  For a more modern and unified account of these results, see
  \cite[Theorems~8.8-8.12]{reutenauer93}.
\end{Remark}

The following conjecture due to Sundaram was originally stated in terms of the multiplicity of
$S^\lambda$ in $1\ind_{C_n}^{S_n}$.

\begin{Conjecture}[\cite{sundaram16}]
  \label{conj:sundaram}
  Let $\lambda \vdash n$ and $n \geq 1$. Then $a_{\lambda, 0}$ is positive except in
  the following cases, when it is zero: $n > 1$ and
  \begin{itemize}
    \item $\lambda = (n-1, 1)$
    \item $\lambda = (2, 1^{n-2})$ when $n$ is odd
    \item $\lambda = (1^n)$ when $n$ is even.
  \end{itemize}
\end{Conjecture}

\noindent \Cref{conj:sundaram} is the $r=0$ case of the following theorem, which is
our main result.

\begin{Theorem}
  \label{thm:main}
  Let $\lambda \vdash n$ and $n \geq 1$. Then $a_{\lambda, r}$ is positive except in
  the following cases, when it is zero: $n > 1$ and
  \begin{itemize}
    \item $\lambda = (2, 2)$, $r = 1, 3$; or $\lambda = (2, 2, 2)$, $r = 1, 5$;
      or $\lambda = (3, 3)$, $r = 2, 4$;
    \item $\lambda = (n-1, 1)$ and $r=0$;
    \item $\lambda = (2, 1^{n-2})$,
      $r = \begin{cases}
                0 & \text{if $n$ is odd} \\
                \frac{n}{2} & \text{if $n$ is even};
              \end{cases}$
    \item $\lambda = (n)$, $r \in \{1, \ldots, n-1\}$;
    \item $\lambda = (1^n)$,
      $r \in \begin{cases}
                  \{1, \ldots, n-1\} & \text{if $n$ is odd} \\
                  \{0, \ldots, n-1\} - \{\frac{n}{2}\} & \text{if $n$ is even}.
                \end{cases}$
  \end{itemize}
  Equivalently, using \Cref{thm:mults}, every irreducible representation appears in each
  $\chi^r\ind_{C_n}^{S_n}$ or $S^\lambda\res_{C_n}^{S_n}$ except in the noted exceptional
  cases.
\end{Theorem}

Our main tool is the following well-known representation-theoretic formula. See
\Cref{sec:formula} for further discussion of its origins and a generalization. Let
$\chi^\lambda(\mu)$ denote the character of $S^\lambda$ at a permutation of cycle type
$\mu$. Write $f^\lambda := \chi^\lambda(1^n) = \dim S^\lambda = \#\SYT(\lambda)$.

\begin{Theorem}
  \label{thm:formula}
  Let $\lambda \vdash n$ and $n \geq 1$. For all $r \in \bZ/n$,
    \[ \frac{a_{\lambda,r}}{f^\lambda}
        = \frac{1}{n} + \frac{1}{n} \sum_{\substack{\ell \mid n \\ \ell \neq 1}}
           \frac{\chi^\lambda(\ell^{n/\ell})}{f^\lambda} c_\ell(r) \]
  where
    \[ c_\ell(r) := \mu\left(\frac{\ell}{\gcd(\ell, r)}\right)
        \frac{\phi(\ell)}{\phi(\ell/\gcd(\ell, r))} \]
  is a Ramanujan sum, $\mu$ is the classical M\"obius function, and
  $\phi$ is Euler's totient function.
\end{Theorem}

We estimate the quotients in the preceding formula using the following result due to Fomin and
Lulov. A \textit{ribbon} is a connected skew shape with no $2 \times 2$ rectangles.

\begin{Theorem}[{\cite[Theorem~1.1]{fl95}}]
  \label{thm:fl_bound}
  Let $\lambda \vdash n$ where $n = \ell s$. Suppose $\lambda$ can be written as
  $s$ successive ribbons each of length $\ell$. Then
    \[ |\chi^\lambda(\ell^s)| \leq \frac{s! \ell^s}{(n!)^{1/\ell}} (f^\lambda)^{1/\ell}. \]
\end{Theorem}

\Cref{thm:fl_bound} is based on the following generalization of the hook length
formula (the $\ell=1$ case), which seems less well-known than it deserves. For $\lambda \vdash
n$, write $c \in \lambda$ to mean that $c$ is a cell in $\lambda$. Further write $h_c$ for the 
\textit{hook length} of $c$ and write $[n] := \{1, 2, \ldots, n\}$.

\begin{Theorem}[{\cite[Corollary~2.2]{fl95}; see also \cite[2.7.32]{jk81}}]
  \label{thm:hook}
  Let $\lambda \vdash n$ where $n = \ell s$. Then
  \begin{equation}
    \label{eq:hook_prod}
    |\chi^\lambda(\ell^s)|
        = \frac{\prod\limits_{\substack{i \in [n] \\ i \equiv_\ell 0}} i}
                   {\prod\limits_{\substack{c \in \lambda \\ h_c \equiv_\ell 0}} h_c}
  \end{equation}
  whenever $\lambda$ can be written as $s$ successive ribbons of length
  $\ell$, and $0$ otherwise.
\end{Theorem}

We also give the following asymptotic uniform distribution result which largely
strengthens \Cref{thm:main}.

\begin{Theorem}
  \label{thm:dist}
  Let $\lambda \vdash n$ be a partition where $f^\lambda \geq n^5 \geq 1$.
  Then for all $r$,
    \[ \left|\frac{a_{\lambda, r}}{f^\lambda} - \frac{1}{n}\right| < \frac{1}{n^2}. \]
  In particular, if $n \geq 81$, $\lambda_1 < n-7$, and $\lambda_1' < n-7$, then
  $f^\lambda \geq n^5$ and the inequality holds.
\end{Theorem}

Indeed, the upper bound in \Cref{thm:dist} is quite weak and is intended only to convey the
flavor of the distribution of $(a_{\lambda, r})_{r=0}^{n-1}$ for fixed $\lambda$. One may use 
Roichman's asymptotic estimate \cite{roichman96} of $|\chi^\lambda(\ell^s)|/f^\lambda$ 
to prove exponential decay in many cases. Moreover, one typically expects $f^\lambda$ to
grow super-exponentially, i.e.~like $(n!)^{\epsilon}$ for some $\epsilon > 0$ (see
\cite{ls08} for some discussion and a more recent generalization of Roichman's result),
which in turn would give a super-exponential decay rate in \Cref{thm:dist}. We have no need
for such refined statements and so have not pursued them further.

The rest of the paper is organized as follows. In \Cref{sec:formula} we discuss and generalize
\Cref{thm:formula}. In \Cref{sec:thm_proofs}, we use symmetric group character estimates and a new
estimate involving ``opposite hook products,'' \Cref{lem:h_op}, to deduce our main results, \Cref{thm:main}
and \Cref{thm:dist}. We have omitted proofs from this extended abstract. They
will appear in a forthcoming version of this article \cite{swanson16}.

\section{Generalizing the Main Formula}
\label{sec:formula}

Variations on \Cref{thm:formula} have appeared in the literature numerous times in several
guises, sometimes implicitly (see \cite[Th\'eor\`eme~2.2]{desarmenien90},
\cite[(7)]{klyachko74}, or \cite[7.88(a), p.~541]{ec2}). In this section we write out a precise 
and relatively general version of these results which explicitly connects \Cref{thm:formula} to
the well-known corresponding symmetric function expansion due to H.~O.~Foulkes.
Let $\Ch$ denote the Frobenius characteristic map, and let $p_\lambda$
denote the power symmetric function indexed by the partition $\lambda$.

\begin{Theorem}[{\cite[Theorem 1]{foulkes72}}]
  \label{thm:chir_p}
  Suppose $\lambda \vdash n \geq 1$ and $r \in \bZ/n$. In this case,
  \begin{equation}
    \label{eq:chir_p}
    \Ch \chi^r\ind_{C_n}^{S_n} = \frac{1}{n} \sum_{\ell \mid n} c_\ell(r) p_{(\ell^{n/\ell})}.
  \end{equation}
\end{Theorem}

The following straightforward result connects and generalizes \Cref{thm:chir_p} and
\Cref{thm:formula}.

\begin{Theorem}
  \label{thm:ind_mults}
  Let $H$ be a subgroup of $S_n$, and let $M$ be a finite-dimensional $H$-module with
  character $\chi^M \colon H \to \bC$. Then
  \begin{equation}
    \label{eq:M_p}
    \Ch M\ind_H^{S_n} = \frac{1}{|H|} \sum_{\mu \vdash n} c_\mu p_\mu
  \end{equation}
  and, for all $\lambda \vdash n$,
  \begin{equation}
    \label{eq:M_mult}
    \langle M\ind_H^{S_n}, S^\lambda\rangle = \frac{1}{|H|} \sum_{\mu \vdash n}
        c_\mu \chi^\lambda(\mu),
  \end{equation}
  where
    \[ c_\mu := \sum_{\substack{h \in H\\\tau(h)=\mu}} \chi^M(h) \]
  and $\tau(\sigma)$ denotes the cycle type of the permutation $\sigma$.
\end{Theorem}

\Cref{thm:ind_mults} is an immediate consequence of the induced character formula.
Note that \eqref{eq:M_p} specializes to \Cref{thm:chir_p} and \eqref{eq:M_mult} specializes to
\Cref{thm:formula} when $M = \chi^r$. In that case, the only possibly non-zero $c_\mu$
arise from $\mu = (\ell^{n/\ell})$ for $\ell \mid n$.

One may consider analogues of the counts $a_{\lambda, r}$ obtained by inducing other
one-dimensional representations of subgroups of $S_n$. Motivated by the study of so-called
higher Lie modules, there is a natural embedding of reflection groups $C_a \wr S_b
\hookrightarrow S_{ab}$. A classification analogous to Klyachko's result, \Cref{thm:kly}, was
asserted for $b=2$ by Schocker \cite[Theorem 3.4]{schocker03}, though the
``rather lengthy proof'' making ``extensive use of routine applications of the
Littlewood-Richardson rule and some well-known results from the theory of plethysms'' was
omitted. By contrast, our approach using \Cref{thm:ind_mults} may be pushed through in this
case using an appropriate generalization of the Fomin-Lulov
bound, \Cref{thm:fl_bound}, such as \cite[Theorem 1.1]{ls08}, resulting in analogues of
\Cref{thm:main} and \Cref{thm:dist}. Our approach begins to break down when $b$ is large 
relative to $n=ab$ and \eqref{eq:M_mult} has many terms. However, we have no current need 
for such generalizations and so have not pursued them further.

\section{Proof of the Main Result}
\label{sec:thm_proofs}

We now summarize our proof of \Cref{thm:main} and
\Cref{thm:dist}. We begin by giving a sufficient condition in terms of upper bounds on
symmetric group character ratios, \Cref{lem:phi_d}, which in turn reduces to a sufficient
condition in terms of lower bounds on $f^\lambda$, \Cref{cor:n_cubed}. We then give an
inequality between hook length products and ``opposite'' hook length products,
\Cref{lem:h_op}, from which one can classify $\lambda$ for which $f^\lambda < n^3$. \Cref{thm:main}
follows in almost all cases, with the remainder being handled by brute
force and case-by-case analysis. \Cref{thm:dist} is similar, except the bound
$f^\lambda < n^5$ is used.

\begin{Lemma}
  \label{lem:phi_d}
  Let $\lambda \vdash n$ and $d \in \bR$. Suppose for all $1 \neq \ell \mid n$ where
  $\lambda$ may be written as $s := n/\ell$ successive ribbons each of length $\ell$ that
  \begin{equation}
    \label{eq:ratio_ub}
    \frac{|\chi^\lambda(\ell^s)|}{f^\lambda} \leq \frac{1}{n^d \phi(\ell)}.
  \end{equation}
  Then for all $r \in \bZ/n$,
    \[ \left|\frac{a_{\lambda, r}}{f^\lambda} - \frac{1}{n}\right| < \frac{1}{n^d}. \]
\end{Lemma}

\Cref{lem:phi_d} follows from \Cref{thm:formula}. The following corollary to
\Cref{lem:phi_d} follows from \Cref{thm:fl_bound} and Stirling's approximation
\cite[(1.53)]{spencer14}.

\begin{Corollary}
  \label{cor:n_cubed}
  Let $\lambda \vdash n$. If $f^\lambda \geq n^3 \geq 1$, then
  $a_{\lambda,r} \neq 0$.
\end{Corollary}

We next summarize techniques that are well-adapted to classifying $\lambda \vdash n$
for which $f^\lambda < n^d$ for fixed $d$. We begin with a curious observation,
\Cref{lem:h_op}, which we have not been able to locate in the literature (though contrast it
with \cite[Theorem~2.3]{fl95}).

\begin{Definition}
  Consider a partition $\lambda = (\lambda_1, \ldots, \lambda_m)$ with
  $\lambda_1 \geq \lambda_2 \geq \cdots \geq 0$ as a set of cells
    \[ \lambda = \{(a, b) \in \bZ \times \bZ : 1 \leq b \leq m, 1 \leq a \leq \lambda_b\}. \]
  Given a cell $c = (a, b) \in \lambda \subset \bN \times \bN$, the
  \textit{opposite hook length} $h_c^{\op}$ at $c$ is $a+b-1$. For instance,
  the unique cell in $\lambda = (1)$ has opposite hook length $1$, and the opposite hook
  length increases by $1$ for each north or east step (using French notation).
\end{Definition}

It is easy to see that $\sum_{c \in \lambda} h_c^{\op} = \sum_{c \in \lambda} h_c$.
On the other hand, we have the following.

\begin{Lemma}
  \label{lem:h_op}
  For all partitions $\lambda$,
    \[ \prod_{c \in \lambda} h_c^{\op} \geq \prod_{c \in \lambda} h_c. \]
  Moreover, equality holds if and only if $\lambda$ is a rectangle.
\end{Lemma}

Our proof of \Cref{lem:h_op} involves considering contributions of the (co-)arm and (co-)leg lengths of
each cell. It would be interesting to find a more conceptual explanation for \Cref{lem:h_op}, perhaps
using representation theory. The appearance of rectangles is particularly striking. Note,
however, that $n!/\prod_{c \in \lambda} h_c^{\op}$ need not be an integer. In any case, we
continue towards \Cref{thm:main}.

\begin{Definition}
  Define the \textit{diagonal preorder} on partitions as follows. Declare $\lambda 
  \lesssim^{\diag} \mu$ if and only if for all $i \in \bP$,
    \[ \#\{c \in \lambda : h_c^{\op} \geq i\} \leq \#\{d \in \mu : h_d^{\op} \geq i\}. \]
\end{Definition}

Note that $\lesssim^{\diag}$ is reflexive and transitive, though not anti-symmetric, so the
diagonal preorder is not a partial order. A straightforward consequence of the definition is that
\begin{equation}
  \label{eq:diag_preorder}
  \lambda \lesssim^{\diag} \mu \qquad \Rightarrow \qquad
      \prod_{c \in \lambda} h_c^{\op} \leq \prod_{d \in \mu} h_d^{\op}.
\end{equation}
Hooks are maximal elements of the diagonal preorder in a sense we next make precise.

\begin{Definition}
  \label{def:diagonal_excess}
  Let $\lambda \vdash n$ for $n \geq 1$. The \textit{diagonal excess} of $\lambda$
  is
    \[ N(\lambda) := |\lambda| - \#\{h_c^{\op} : c \in \lambda\}. \]
\end{Definition}

\noindent For instance, $\lambda = (3, 3)$ has opposite hook lengths ranging from $1$ to 
$4$, so $N((3, 3)) = 6 - 4 = 2$.

\begin{Example}
  \label{ex:hook_diagonals}
  Let $\lambda \vdash n$ be a hook. Consider the sequence
  $(\#\{c \in \lambda : h_c^{\op} = i\})_{i=1}^\infty$ recording the number of cells with 
  opposite hook lengths $1, 2, 3, \ldots$. This sequence is
    \[ (1, 2, 2, \ldots, 2, 1, \ldots, 1, 0, 0, \ldots) \]
  where there are $N(\lambda)$ two's and $n -  N(\lambda)$ non-zero entries. In particular, 
  $N(\lambda) + 1 \leq n - N(\lambda)$, i.e.~$2N(\lambda)+1 \leq n$.
\end{Example}

\begin{Proposition}
  \label{prop:h_op}
  Let $\lambda \vdash n$ for $n \geq 1$. Set 
  \begin{equation}
    \label{eq:N}
    N :=
        \begin{cases}
          N(\lambda) & \text{if }2N(\lambda)+1 \leq n \\
          \left\lfloor\frac{n-1}{2}\right\rfloor & \text{if }2N(\lambda)+1 > n.
        \end{cases}
  \end{equation}
  Then
  \begin{equation}
    \label{eq:diag_hook}
    \lambda \lesssim^{\diag} (n-N, 1^N).
  \end{equation}
  In particular, if $2N(\lambda) + 1 \leq n$, then the hook $(n - N(\lambda), 1^{N(\lambda)})$
  is maximal for the diagonal preorder on partitions of size $n$ with diagonal excess
  $N(\lambda)$.
\end{Proposition}

Our proof of \Cref{prop:h_op} is algorithmic. Each step of the algorithm goes up in the diagonal preorder
and the algorithm terminates at an appropriate hook. The following corollary of \Cref{prop:h_op} and
\Cref{lem:h_op} essentially gives a polynomial lower bound on $f^\lambda$ in terms of the diagonal excess.

\begin{Corollary}
  \label{cor:h_op}
  Let $\lambda \vdash n$ for $n \geq 1$, and take $N$ as in \eqref{eq:N}. For any
  $0 \leq M \leq N$, we have
  \begin{equation}
    \label{eq:h_op_bound}
    \prod_{c \in \lambda} h_c^{\op} \leq (n-M)! (M+1)!.
  \end{equation}
  Indeed,
  \begin{equation}
    \label{eq:f_la_binom}
    f^\lambda \geq \frac{1}{M+1} \binom{n}{M}.
  \end{equation}
\end{Corollary}

We now sketch the proof of \Cref{thm:main}, the proof of \Cref{thm:dist} being similar.
\Cref{thm:main} follows from \Cref{cor:n_cubed} except when $f^\lambda < n^3$.
One may classify these exceptional $\lambda$ using the bound \eqref{eq:f_la_binom} from
\Cref{cor:h_op} for $n$ sufficiently large as essentially those $\lambda$ with
$N(\lambda) \leq 4$.
The result is twelve pairs of infinite families, namely the concatenations
$(n-M) \oplus \mu$ for $\mu \vdash M \leq 4$ and their conjugates. For example,
one such pair is $\{(n-4, 3, 1)\}$ and its conjugate. The five pairs with $M=4$ all result in
$f^\lambda \geq n^3$ for $n \geq 34$. The conclusion of \Cref{thm:main} may be verified by
hand for the remaining seven families for $n \geq 15$. One must then verify the conclusion of
\Cref{thm:main} for $n \leq 33$, which takes little time on modern computers.

\acknowledgements{
The author would like to thank Sheila Sundaram for sharing a preprint of \cite{sundaram16}
which motivated the present work. He would also like to thank his advisor, Sara Billey, for her
support, insightful comments, and a careful reading of the manuscript; his partner, R.~Andrew
Ohana, for numerous fruitful discussions and support, including an early observation which lead
to an alternate proof of \Cref{thm:hook}; and Connor Ahlbach for valuable discussions on related work.
}

\printbibliography


\end{document}
